#ifndef BBFS_H_
#define BBFS_H_

#include <algorithm>
#include <cstddef>
#include <cstdlib>
#include <string>
#include <unordered_set>
#include <vector>


namespace lxj
{
// 单词接龙
// 字典 wordList 中从单词 beginWord 和 endWord 的 转换序列
// 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk ：
// 每一对相邻的单词只差一个字母。
// 对于 1 <= i <= k 时，每个 si 都在 wordList 中
// 注意， beginWord 不需要在 wordList 中。sk == endWord
// 给你两个单词 beginWord 和 endWord 和一个字典 wordList
// 返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目
// 如果不存在这样的转换序列，返回 0 。
// 测试链接 : https://leetcode.cn/problems/word-ladder/
inline int ladderLength(std::string               beginWord,
                        std::string               endWord,
                        std::vector<std::string>& wordList)
{
    std::unordered_set<std::string> dict(wordList.begin(), wordList.end());
    if (dict.count(endWord) == 0) return 0;

    std::unordered_set<std::string> smallLevel, bigLevel, nextLevel;
    smallLevel.insert(beginWord);
    bigLevel.insert(endWord);
    for (int len = 2; !smallLevel.empty(); len++) {
        for (std::string word : smallLevel) {
            for (int i = 0; i < word.size(); i++) {
                char old = word[i];
                for (char ch = 'a'; ch <= 'z'; ch++) {
                    if (ch != old) {
                        word[i] = ch;
                        if (bigLevel.count(word)) return len;
                        if (dict.count(word) != 0) {
                            dict.erase(word);
                            nextLevel.insert(word);
                        }
                    }
                }
                word[i] = old;
            }
        }
        if (nextLevel.size() <= bigLevel.size()) {
            auto& tmp  = smallLevel;
            smallLevel = nextLevel;
            nextLevel  = tmp;
        }
        else {
            auto& tmp  = smallLevel;
            smallLevel = bigLevel;
            bigLevel   = nextLevel;
            nextLevel  = tmp;
        }
        nextLevel.clear();
    }
    return 0;
}

// 牛牛的背包问题 & 世界冰球锦标赛
// 牛牛准备参加学校组织的春游, 出发前牛牛准备往背包里装入一些零食, 牛牛的背包容量为w。
// 牛牛家里一共有n袋零食, 第i袋零食体积为v[i]。
// 牛牛想知道在总体积不超过背包容量的情况下,他一共有多少种零食放法(总体积为0也算一种放法)。
// 输入描述：
// 输入包括两行
// 第一行为两个正整数n和w(1 <= n <= 30, 1 <= w <= 2 * 10^9),表示零食的数量和背包的容量
// 第二行n个正整数v[i](0 <= v[i] <= 10^9),表示每袋零食的体积
// 输出描述：
// 输出一个正整数, 表示牛牛一共有多少种零食放法。
// 测试链接 : https://www.luogu.com.cn/problem/P4799
class Plan {
    inline static int                    MAXN = 40;
    inline static int                    MAXM = 1 << 20;
    inline static std::vector<long long> lsum = std::vector<long long>(MAXM);
    inline static std::vector<long long> rsum = std::vector<long long>(MAXM);

    std::vector<long long> arr;

    inline void build(const std::vector<long long>& ticket)
    {
        arr     = ticket;
        int len = arr.size();
        len     = 1 << (len / 2);
        std::fill(lsum.begin(), lsum.begin() + len, 0);
        std::fill(rsum.begin(), rsum.begin() + len, 0);
    }

    inline int f(int l, int r, long long s, long long w, std::vector<long long>& ans, int j)
    {
        if (s > w) return j;
        if (l == r) {
            ans[j++] = s;
        }
        else {
            j = f(l + 1, r, s, w, ans, j);
            j = f(l + 1, r, s + arr[l], w, ans, j);
        }
        return j;
    }

public:
    inline long long planCnt(long long property, const std::vector<long long>& ticket)
    {
        build(ticket);
        size_t len   = arr.size();
        int    lsize = f(0, len >> 1, 0, property, lsum, 0);
        int    rsize = f(len >> 1, len, 0, property, rsum, 0);
        std::sort(lsum.begin(), lsum.begin() + lsize);
        std::sort(rsum.begin(), rsum.begin() + rsize);
        long long ans = 0;
        for (int i = lsize - 1, j = 0; i >= 0; i--) {
            while (j < rsize && lsum[i] + rsum[j] <= property) j++;
            ans += j;
        }
        return ans;
    }
};

// 最接近目标值的子序列和
// 给你一个整数数组 nums 和一个目标值 goal
// 你需要从 nums 中选出一个子序列，使子序列元素总和最接近 goal
// 也就是说，如果子序列元素和为 sum ，你需要 最小化绝对差 abs(sum - goal)
// 返回 abs(sum - goal) 可能的 最小值
// 注意，数组的子序列是通过移除原始数组中的某些元素（可能全部或无）而形成的数组。
// 数据量描述:
// 1 <= nums.length <= 40
// -10^7 <= nums[i] <= 10^7
// -10^9 <= goal <= 10^9
// 测试链接 : https://leetcode.cn/problems/closest-subsequence-sum/
class ClosestSubsequenceSum {
    inline static int              MAXN = 40;
    inline static int              MAXM = 1 << 20;
    inline static std::vector<int> lsum = std::vector<int>(MAXM);
    inline static std::vector<int> rsum = std::vector<int>(MAXM);
    inline static int              fill = 0;

    inline void collect(const std::vector<int>& nums, int l, int r, int s, std::vector<int>& sum)
    {
        if (l == r) {
            sum[fill++] = s;
        }
        else {
            int j = l + 1;
            while (j < r && nums[j] == nums[l]) j++;
            for (int k = 0; k <= j - l; k++) {
                collect(nums, j, r, s + k * nums[l], sum);
            }
        }
    }

public:
    inline int minAbsDifference(std::vector<int>& nums, int goal)
    {
        int       n   = nums.size();
        long long min = 0;
        long long max = 0;
        for (auto& i : nums) {
            i >= 0 ? max += i : min += i;
        }
        if (max < goal) return goal - max;
        if (min > goal) return min - goal;

        std::sort(nums.begin(), nums.end());
        fill = 0;
        collect(nums, 0, n >> 1, 0, lsum);
        int lsize = fill;
        fill      = 0;
        collect(nums, n >> 1, n, 0, rsum);
        int rsize = fill;
        std::sort(lsum.begin(), lsum.begin() + lsize);
        std::sort(rsum.begin(), rsum.begin() + rsize);
        int ans = std::abs(goal);
        for (int i = 0, j = rsize - 1; i < lsize; i++) {
            while (j > 0 &&
                   std::abs(goal - lsum[i] - rsum[j - 1]) <= std::abs(goal - lsum[i] - rsum[j]))
                j--;
            ans = std::min(ans, std::abs(goal - lsum[i] - rsum[j]));
        }
        return ans;
    }
};
}   // namespace lxj

#endif